package com.hy.treeNode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class FillTreeNodeRightPoint {


    /**
     * 116.填充每个节点的下一个右侧节点指针
     * 力扣题目链接
     *
     * 给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
     *
     * 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
     *
     * 初始状态下，所有 next 指针都被设置为 NULL。
     *
     * 输入 [1,2,3,4,5,6,7]
     * 输出 [1,#,2,3,#,4,5,6,7,#]
     */
    public PerfectTreeNode fillTreeNodeRightPoint(PerfectTreeNode root){
        Deque<PerfectTreeNode> deque = new LinkedList<>();
        if (root != null){
            deque.addLast(root);
        }

        while (!deque.isEmpty()){
            int len = deque.size();
            PerfectTreeNode cur = deque.poll();

            if (cur.left != null){
                deque.addLast(cur.left);
            }
            if (cur.right != null){
                deque.addLast(cur.right);
            }
            for (int i = 1; i < len; i++) {
                PerfectTreeNode next = deque.poll();
                if (next.left != null){
                    deque.addLast(next.left);
                }
                if (next.right != null){
                    deque.addLast(next.right);
                }
                cur.next = next;
                cur = next;
            }
        }
        return root;
    }

    public static void main(String[] args) {
        PerfectTreeNode leftNode1 = new PerfectTreeNode(1, null, null,null);
        PerfectTreeNode rightNode1 = new PerfectTreeNode(2, null, null,null);

        PerfectTreeNode leftNode2 = new PerfectTreeNode(6, null, null,null);
        PerfectTreeNode rightNode2 = new PerfectTreeNode(8, null, null,null);

        PerfectTreeNode leftNode = new PerfectTreeNode(4, leftNode1, rightNode1,null);
        PerfectTreeNode rightNode = new PerfectTreeNode(7, leftNode2, rightNode2,null);

        PerfectTreeNode root = new PerfectTreeNode(5, leftNode, rightNode,null);
        FillTreeNodeRightPoint fillTreeNodeRightPoint = new FillTreeNodeRightPoint();

        System.out.println("res: "+fillTreeNodeRightPoint.fillTreeNodeRightPoint(root));
    }
}
